package binaryTree;


import java.util.*;

public class D230721 {
    // 判断是不是完全二叉树
    public boolean isCompleteTree (TreeNode root) {
        // ArrayDeque<>() 不允许加入的元素为空（报空指针异常）
        // LinkedList<>() 允许加入 null
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                // 不为空， 加入左右孩子
                queue.add(cur.left);
                queue.add(cur.right);
            } else {
                // 当前节点为空，按照完全二叉树的性质，后续不能再有节点
                break;
            }
        }
        while (!queue.isEmpty()) {
            if (queue.poll() != null) {
                // 后续还有节点，返回false
                return false;
            }
        }
        return true;
    }

    public boolean isCompleteTree2 (TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            // 因为 ArrayDeque 不能存 null
            // 所以用值为 -1 来表示 null
            if (cur.val == -1) {
                // 当前节点为空
                break;
            }
            if (cur.left != null) {
                queue.add(cur.left);
            } else {
                queue.add(new TreeNode(-1));
            }
            if (cur.right != null) {
                queue.add(cur.right);
            } else {
                queue.add(new TreeNode(-1));
            }
        }
        while (!queue.isEmpty()) {
            if (queue.poll().val != -1) {
                return false;
            }
        }
        return true;
    }


    // 判断是不是平衡二叉树
    // 递归遍历每一个节点
    // 计算每个节点的左右子树的高度
    // 相差大于1，则不是平衡二叉树
    public boolean IsBalanced_Solution (TreeNode pRoot) {
        if (pRoot == null) {
            return true;
        }
        int left = deep(pRoot.left);
        int right = deep(pRoot.right);

        if (Math.abs(left - right) > 1) {
            return false;
        }

        return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);
    }

    int deep(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = deep(root.left);
        int right = deep(root.right);
        return (left > right) ? left + 1 : right + 1;
    }


    // 二叉搜索树的最近公共祖先
    // 方法一：非递归
    // 利用二叉搜索数的性质，分别寻找两个节点，并记录路径
    // 同时遍历两个路径，最后一个相等的，就是最近公共祖先
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        List<Integer> p_path = new ArrayList<>();
        List<Integer> q_path = new ArrayList<>();

        // 寻找左边的 p，记录寻找的路径
        TreeNode cur = root;
        while (cur.val != p) {
            p_path.add(cur.val);
            if (cur.val > p) cur = cur.left;
            else cur = cur.right;
        }
        p_path.add(cur.val);    // p 也要加入路径，因为一个节点也可以是它自己的祖先，就是说有可能为答案

        // 寻找右的 q，记录寻找的路径
        cur = root;
        while (cur.val != q) {
            q_path.add(cur.val);
            if (cur.val > q) cur = cur.left;
            else cur = cur.right;
        }
        q_path.add(cur.val);

        int ret = 0;
        int minSize = Math.min(p_path.size(), q_path.size());
        for (int i = 0; i < minSize; i++) {
            if (p_path.get(i).equals(q_path.get(i))) {
                ret = p_path.get(i);
            } else {
                break;
            }
        }
        return ret;
    }

    // 在二叉树中找到两个节点的最近公共祖先
    // 方法一：递归
    public int lowestCommonAncestor2 (TreeNode root, int o1, int o2) {
        if (root == null) {
            return -1;
        }
        if (root.val ==  o1|| root.val == o2) {
            // 找到 p 或 q
            return root.val;
            // 这也顺便解决了自己就是最近公共祖先的问题
        }
        int left = lowestCommonAncestor2(root.left, o1, o2);
        int right = lowestCommonAncestor2(root.right, o1, o2);

        if (left != -1 && right != -1) {
            // 当前节点是最近公共祖先
            return root.val;
        } else if (left == -1) {
            return right;
        } else {
            return left;
        }
    }

    // 方法二：分别找 p 和 q，记录路径，然后对比两条路径，定位最近公共祖先
    // 寻找方法，dfs寻找，如果到叶子节点还没找到，回溯时去除刚刚加入的节点。

    //记录是否找到到o的路径
    public boolean flag = false;
    //求得根节点到目标节点的路径
    public void dfs(TreeNode root, ArrayList<Integer> path, int o){
        if(flag || root == null)
            return; // 路径寻找完毕 或者 root == null

        path.add(root.val); // 加入路径
        if(root.val == o){
            // 找到
            flag = true;
            return;
        }
        //dfs遍历查找左右子树
        dfs(root.left, path, o);
        dfs(root.right, path, o);
        //查找完左右子树，找到了就返回
        if(flag)
            return;
        //没找到，就删除当前节点，回溯
        path.remove(path.size() - 1);
    }
    public int lowestCommonAncestor3 (TreeNode root, int o1, int o2) {
        ArrayList<Integer> path1 = new ArrayList<Integer>();
        ArrayList<Integer> path2 = new ArrayList<Integer>();
        //求根节点到两个节点的路径
        dfs(root, path1, o1);
        //重置flag，查找下一个
        flag = false;
        dfs(root, path2, o2);
        int res = 0;
        //比较两个路径，找到第一个不同的点
        for(int i = 0; i < path1.size() && i < path2.size(); i++){
            int x = path1.get(i);
            int y = path2.get(i);
            if(x == y)
                //最后一个相同的节点就是最近公共祖先
                res = x;
            else
                break;
        }
        return res;
    }
}
